package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/3 21:30
 */
public class 完全二叉树的节点个数 {
    //https://leetcode.cn/problems/count-complete-tree-nodes/
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;

        TreeNode l = root, r = root;
        int hl = 1, hr = 1;
        while (l.left != null) {
            l = l.left;
            hl++;
        }

        while (r.right != null) {
            r = r.right;
            hr++;
        }

        if (hr == hl) {
            return (1 << hr) - 1;
        }
        return countNodes(root.right) + countNodes(root.left) + 1;
    }


}
